// @algorithm @lc id=803 lang=cpp 
// @title cheapest-flights-within-k-stops


// #define print(...)
// @test(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)=200
// @test(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,0)=500
#define INF (INT_MAX>>1)
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> dp(k+2, vector<int>(n+1, INF));
        dp[0][src] = 0;
        for(int via=1; via<=k+1; via++){
            for(auto &f : flights){
                int from=f[0], to=f[1], price=f[2];
                dp[via][to] = min(dp[via][to], dp[via-1][from] + price);
            }
        }
        int ans = INF;
        for(int via=1; via<=k+1; via++)
            ans = min(ans, dp[via][dst]);
        return ans==INF?-1:ans;
    }
};